﻿// 7-19 交换二叉树中每个结点的左孩子和右孩子 (20分).cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

// 7-11 前序序列创建二叉树 (25 分).cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//user:LDC
//date:20191217 21:22
//level:7
//key:1.交换每一个节点的左右节点，通过层序遍历去找，不要先序遍历

#include <iostream>
#include<string>
#include <stack>
#include <queue>
#include <vector>
using namespace std;
class tree
{

public:
	char inf;
	tree* l;
	tree* r;
	tree()
	{
		inf = 0;
		tree* lchild = NULL;
		tree* rchild = NULL;

	}

	void visit(string s, int& i) {//每一次循环中都引用了i来调整读取字符串中的下一个字符
		//cin >> data;
		inf = s[i];
		i++;
		if (inf != '#') {
			this->l = new tree;
			this->r = new tree;
		}
	}
	void visit_read() {
		if (inf != '#')
		{
			cout << inf;
			/*if (1) { cout << " "; }*/
		}

	}
	void visit_next_read() {

		cout << inf;

	}
	void pretraversal(tree* proot, string s, int& i) {//把字符串传入，是不是引用都无所谓
		if (NULL != proot)
		{
			(proot)->visit(s, i);
			pretraversal(proot->l, s, i);
			pretraversal(proot->r, s, i);
		}
	}
	void pretraversal_read(tree* proot) {
		if (NULL != proot)
		{
			(proot)->visit_read();
			pretraversal_read(proot->l);
			pretraversal_read(proot->r);
		}
	}
	void pretraversal_middle_read(tree* proot) {
		if (NULL != proot)
		{
			pretraversal_middle_read(proot->l);
			(proot)->visit_read();
			pretraversal_middle_read(proot->r);
		}
	}

};
void op(tree* p)
{
	tree* t;
	t = p->l;
	p->r = p->l;
	p->l = t;

}
void op_middle_read(tree* proot) {
	if (NULL != proot)
	{
		op_middle_read(proot->l);
		op(proot);
		op_middle_read(proot->r);
	}
}



int main() {
	int i = 0;
	string s;
	queue<tree*>k;
	char c;
	while ((c = getchar()) != EOF)
	{
		getline(cin, s);
		s.insert(0, 1, c);
		i = 0;
		tree* head = new tree;
		head->pretraversal(head, s, i);//建立二叉树

		head->pretraversal_middle_read(head);//遍历二叉树
		k.push(head);
		tree* p = new tree;
		while (!k.empty()) {
			if (k.front()->l != NULL) { k.push(k.front()->l); }
			if (k.front()->r != NULL) {
				k.push(k.front()->r);
			}
			p = k.front()->l;
			k.front()->l = k.front()->r;
			k.front()->r = p;
			k.pop();
			
		}
		cout << "\n";
		head->pretraversal_middle_read(head);//遍历二叉树

		
	}



}

